package com.wtgroup.demo.leetcode.org_bytedance;

import com.wtgroup.demo.common.bean.LinkNode;

/**
 * @author 60906
 * @date 2021/5/4 19:49
 */
public class Q_合并两个有序链表 {

    public static void main(String[] args) {
        Solution exe = new Solution();
        LinkNode l1 = LinkNode.toListNode(1, 2, 3);
        LinkNode l2 = LinkNode.toListNode(1, 2, 4);
        LinkNode res = exe.mergeTwoLists(l1, l2);
        LinkNode.print(res);
    }

    /**
     * LC 递归
     */
    private static class Solution {

        public LinkNode mergeTwoLists(LinkNode l1, LinkNode l2) {
            if (l1 == null) {
                return l2;
            }
            if (l2 == null) {
                return l1;
            }
            if (l1.value <= l2.value) {
                l1.next = mergeTwoLists(l1.next, l2);
                return l1;
            } else {
                l2.next = mergeTwoLists(l1, l2.next);
                return l2;
            }
        }

    }

    /**
     * 递归方式
     * @deprecated 啰嗦
     */
    static class Solution_dep {

        public LinkNode mergeTwoLists(LinkNode l1, LinkNode l2) {
            LinkNode dummy = new LinkNode();
            recurse(l1, l2, dummy);
            return dummy.next;
        }

        private void recurse(LinkNode a, LinkNode b, LinkNode prev) {
            LinkNode next = null;
            if (a==null && b==null) {
                return;
            } else if (a == null) {
                next = b;
                b = b.next;
            } else if (b == null) {
                next = a;
                a = a.next;
            } else {
                if (a.value <= b.value) {
                    next = a;
                    a = a.next;
                } else {
                    next = b;
                    b = b.next;
                }
            }

            prev.next = next;
            recurse(a, b, next);
        }

    }

}
